1. Field of the Invention
The present invention generally relates to virtual storage mechanisms for data processing systems and, more particularly, to an improved directory look-aside table (DLAT) structure which is capable of improved handling of the periodicity of virtual page addresses when processing among multiple data spaces. The invention is specifically directed to the minimization of synonym entries in the DLAT for a system having DLAT entries that can concurrently translate virtual addresses in multiple data spaces into real main storage addresses.
2. Description of the Prior Art
Virtual storage organization and management for data processing systems are described, for example, by Harvey M. Deitel in An Introduction to Operating Systems, Addison-Wesley (1984), by Harold Lorin and Harvey M. Deitel in Operating Systems, Addison-Wesley (1981), and by Harold S. Stone in High-Performance Computer Architecture, Addison-Wesley (1987). In a virtual storage system, paging is a relocation and address-to-physical-location binding mechanism providing the user of the system with what appear to be considerably larger memory spaces than are really available. The key feature of the virtual storage concept is disassociating the addresses referenced in a running process from the addresses available in main storage. The addresses referenced by the running process are called virtual addresses, while the addresses available in main storage are called real addresses. The virtual addresses must be mapped into real addresses as the process executes, and that is the function of the dynamic address translation (DAT) mechanism. One such mechanism employs a directory look-aside table (DLAT), sometimes referred to as a translation look-aside buffer (TLB), which stores recent virtual address translations. For virtual addresses stored in the DLAT, the translation process requires only a single or, at most, a couple of machine cycles. For addresses not stored in the DLAT, the DAT process may take from fifteen to sixty cycles.
Translations from the virtual address to the real address must be made to find where the addressed instruction or data is in main storage. This is typically done on a page basis. In fact, the translations stored in the DLAT are actually only page translations, and the last bits of an address are the location in that page, so only the page address must be translated.
In conventional virtual storage systems, a condition called thrashing can occur wherein the system can do little useful work because of excessive paging. The condition was recognized and discussed, for example, by P. J. Denning in "Thrashing: its Causes and Prevention", AFIPS Conf. Proc., vol. 33, 1968 FJCC, pp. 915-922. Denning maintained that for a program to run efficiently, its working set of pages must be maintained in primary storage; otherwise, thrashing would occur as the program repeatedly requests pages from secondary storage. The condition is mentioned in Deitel, supra, in section 9.5, "Working Sets" in his chapter on Virtual Storage Management.
U.S. Pat. No. 4,136,385 to Gannon et al. addresses the problem with a synonym control for multiple virtual storage systems. The Gannon et al. DLAT synonym control controls the setting of an indicator in each DLAT entry for indicating whether the DLAT entry is to be shared by all user address spaces or is to be restricted to a single address space identified in the DLAT. This is accomplished by means of a common space bit in any segment table entry (STE) or, alternatively, in any page table entry (PTE) in any private address space to indicate whether the segment or page contains programs and data private to the address space or shared by all address spaces. Thus, each DLAT entry contains a common/private storage indicator which is set to the state of the common space bit in the STE or PTE used in an address translation loaded into the DLAT entry. When the entry is read, the private/common storage indicator controls whether the DLAT can only be used by the address space identified in the DLAT or by all address spaces.
Conventional two-way DLAT designs inadequately handle the periodicity of virtual page addresses when processing among multiple data spaces. A typical two-way DLAT design maps identical virtual addresses in all data spaces to the same DLAT row. For example, in the following pseudocode EQU DO i=1 to 1,000 EQU A(i)+B(i)=C(i),
if A, B and C have the same origin (e.g., zero) in each of three data spaces, the code will deliver poor performance due to DLAT thrashing caused by data space synonyms. While the Gannon et al. synonym control eliminates a class of synonym entries by means of a common space bit, it does not address the class of synonym problems in a two-way DLAT produced by three data spaces having the same origin.